package done.easy_601_700;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static java.lang.Math.max;

/**
 * 628. Maximum Product of Three Numbers 三个数的最大乘积
 * <p>
 * 给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 * <p>
 * 示例 1:
 * 输入: [1,2,3]
 * 输出: 6
 * <p>
 * 示例 2:
 * 输入: [1,2,3,4]
 * 输出: 24
 **/
@Slf4j
public class MaximumProductOfThreeNumbers {

    @SuppressWarnings("all")
    public int maximumProduct(int[] nums) {
        // 190528 first
        return -1;
    }

    @Test
    public void test() {
        log.info("{}", maximumProduct(new int[]{1, 2, 3, 4, -5, -6, 5, 6}));
    }
}





























/*
public int maximumProduct(int[] nums) {
    // 快排
    quickSort(nums,0,nums.length - 1);
    // jdk自带排序
    //Arrays.sort(nums);

    // 最后三个连乘，如果都是正数，这三个连乘就是最大的
    // 如果有一个是负数，还是最大的三个正数连乘
    int t1 = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];

    // 前两个连乘，如果有两个以上的负数
    // 最大的正数与最小的两个负数连乘就是最大乘积
    int t2 = nums[nums.length - 1] * nums[0] * nums[1];

    return max(t1, t2);
}

private void quickSort(int[] nums, int left, int right){
    if (left < right) {

        int p = partition(nums, left, right);

        quickSort(nums, left, p - 1);

        quickSort(nums, p + 1, right);
    }
}

private int partition(int[] nums, int left, int right){
    int index = left + 1;

    for (int i = index; i <= right; i++) {
        if (nums[left] > nums[i]) {

            // 元素交换
            swap(nums, index, i);

            index++;
        }
    }

    // 元素交换
    swap(nums, index - 1, left);
    return index - 1;
}

private void swap(int[] nums, int index, int left){
    int temp    = nums[index];
    nums[index] = nums[left];
    nums[left]  = temp;
}
*/
